#include <stdio.h>

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i;       // 初始化最大值索引为根节点
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换并继续调整堆
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest); // 递归调整受影响的子树
    }
}

// 堆排序主函数
void heap_sort(int arr[], int size) {
    // 构建最大堆
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, size, i);
    }

    // 提取元素进行排序
    for (int i = size - 1; i >= 0; i--) {
        // 将当前堆顶元素（最大值）移动到末尾
        swap(&arr[0], &arr[i]);

        // 减少堆的大小，并重新调整堆
        heapify(arr, i, 0);
    }
}

// 测试堆排序
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    heap_sort(arr, size);

    printf("\n\n排序后数组:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}